class Solution {
public:
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};

    int solve(vector<vector<char> >& grid) {
        int count = 0;
        for(int i = 0; i < grid.size(); ++i)
        {
            for(int j = 0; j < grid[0].size(); ++j)
            {
                if(grid[i][j] == '1')
                {
                    count++;
                    grid[i][j] = '0';
                    bfs(grid, i, j);
                }
            }
        }
        return count;
    }

    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pair<int,int>> q;
        q.push({i,j});
        
        while(!q.empty())
        {
            auto [i,j] = q.front();
            q.pop();
            for(int k = 0; k < 4; k++)
            {
                int x = i+dx[k];
                int y = j+dy[k];
                if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size() && grid[x][y] == '1')
                {
                    grid[x][y] = '0';
                    q.push({x,y});
                }
            }
        }
    }
};
